package com.aqie.easy.graph;

/**
 * 997 Find the Town Judge
 */
public class FindJudge {
    /**
     * 1, 7ms
     * @param N
     * @param trust
     * @return
     */
    public int findJudge(int N, int[][] trust) {
        int [][] b = new int[N][2];
        for (int i = 0; i < N; i++) {
            b[i][0] = 0;
            b[i][1] = 0;
        }
        for (int[] aTrust : trust) {
            b[aTrust[0] - 1][0]++;
            b[aTrust[1] - 1][1]++;
        }
        int g = -1;
        for (int i = 0; i < N; i++) {
            if (b[i][0] == 0 && b[i][1] == N -1) {
                if (g != -1) {
                    return -1;
                }
                g = i + 1;
            }
        }
        return g;
    }

    /**
     * 2, 6ms
     * @param N
     * @param trust
     * @return
     */
    public int FindJudge2(int N, int[][] trust) {
        int[] trusts = new int[N + 1];
        int[] trusted = new int[N + 1];

        for (int[] aTrust : trust) {
            trusts[aTrust[0]]++;
            trusted[aTrust[1]]++;
        }

        for (int i = 1; i <= N; i ++) {
            if (trusted[i] == N - 1) {
                if (trusts[i] == 0) {
                    return i;
                }
            }
        }
        return -1;
    }
}
